This invention relates in general to digital data processing and more specifically to accessing, tracking and managing free slots in a list in computer memory.
One basic operation performed often in many of today's computer applications includes keeping track of available memory portions, or “slots.” A slot can be any portion of memory such as, e.g., a byte, word, block of words, data structure, etc. One common way of keeping track of slots is to use a list. A list is, in general, a series of slots or, typically, a list of pointers or flags corresponding to slots. Typically, the slots are adjacent to each other to form a contiguous block of memory. However, some approaches allows slots to be distributed in different parts of memory.
FIG. 1A illustrates slots in a list.
In FIG. 1A, list 10 represents 8 consecutive memory portions. Each portion is a slot with an index from 0-7. List 10 represents the list at time t1. List 20 represents the same list at a later time, t2. Shaded slots indicate slots that have been allocated. Allocated slots are those that are being used by a process such as an application program, operating system, task, or other process. Allocated slots are not currently free to be allocated for another process. The difference between the lists at times t1 and t2 is that slot 2 has been allocated at time t2 whereas it was free at time t1. When a slot is allocated the slot is also set to be “locked.”
Slots can be allocated so that they are provided to a process and locked from use by other processes. Subsequently, slots can be made free, or unlocked, so that they are again available for use by a process. The ability to lock and unlock (i.e., allocate or deallocate) slots is performed often and can be critical to performance of a computer program, especially where the number of slots is large and slots are needed frequently.
In FIG. 1A, list 30 at time t3 is another snapshot of the slot list. At time t3, list 30 now has slots 2, 3, 4, 6 and 7 allocated while slots 0, 1 and 5 are free. Note the changing allocations of slots among the list at times t1, t2 and t3 is arbitrary. At any point in time, depending on process needs, slots can be free or allocated.
The prior art uses several techniques to manage lists of slots. One approach is to use a “freelist.” The freelist is typically an array that indicates whether or not slots are free or allocated. An example of a freelist index array is shown in FIG. 1B. In FIG. 1B, array 40 has a first element at address FREELIST. The array is indexed by providing an offset to the base address, FREELIST. Another variable is FREELIST_SIZE. FREELIST_SIZE is a constant that is the number of slots in FREELIST.
An example of code that manages the FREELIST of FIG. 1B is shown in FIG. 1C. As is known in the art, the code shown in FIG. 1C will return the index to the first free slot as indicated by the values in FREELIST. For example, referring to the list at t1 of FIG. 1A, the routine getFreeElement returns the value 2 since the first free slot in the list (counting from zero upwards) is slot 2. Likewise, if getFreeElement is called at time t2, when the list exists as shown by list 20, getFreeElement returns the value 4. This return index value is used by a process to access the free slot.
A function called releaseElement is used to release slots. A process calls releaseElement with an index of a slot to deallocate. The routine releaseElement sets an indication in FREELIST that the slot corresponding to the index is now free for reallocation.
It should be apparent that the approach described here using the FREELIST and consecutive researching through a freelist for free slots is very time consuming. This approach requires looping with an index through the FREELIST until a first free slot is found. In applications where slots are frequently allocated and deallocated, this approach is prohibitive. Also, if the number of slots is large, the FREELIST can take up a non-trivial amount of memory.
Since the status of a slot can only take on one of two values, i.e., free or locked, the FREELIST can be made up of single-bit values. FIG. 1D illustrates the case where single bits in a word of memory are used to indicate the status of slots. In FIG. 1D, a “one” value in a bit position indicates that a slot is locked, or allocated. A “zero” value in a bit position indicates that the slot is free. FIG. 1D corresponds to list 10 of FIG. 1A. Naturally, the list, slot, FREELIST_SIZE and number of indexes, and other parameters can be of any number, size, type, etc.
Although packing the FREELIST indicators into single bit positions is space-efficient, it causes even more overhead in managing the FREELIST. This is because bit manipulation such as masking, shifting, converting, etc. are necessary to successfully check a bitmapped freelist and return an index. Although many computer systems provide specialized instructions for doing bit manipulations, the use of these instructions still presents a considerable overhead to freelist management.
One problem with a bit mapped freelist is that most computers operate on digital data in an arithmetic mode where bit positions are converted to, and correspond to, binary values. FIG. 1D shows bit values at the top of word 50, while bit positions are shown below the word. Converting arithmetic bit value numbers to bit position values and freelist indexes is time-consuming.
Other approaches for list management include the use of single, or double-linked list, stack, keeps, etc. All of these approaches include drawbacks either by increasing the memory space required to support these schemes, or in central processing unit (CPU) cycles to perform additional processing to manage the system.